package com.gushuang.leetcode;

import java.util.*;
//https://leetcode.cn/problems/sliding-window-maximum
public class slidingWindowMaximum {
    public int[] maxSlidingWindow(int[] nums, int k) {
      if(nums==null||nums.length==0) return new int[0];
      int n=nums.length;
      int[] result = new int[n-k+1];
      Deque<Integer> deque=new LinkedList<>();
        for (int i = 0; i < n; i++) {
            // 移除不在滑动窗口内的元素
            if(!deque.isEmpty()&& deque.peekFirst() < i-k+1){
                deque.pollFirst();
            }
            // 移动队列中所有小于当前元素的元素
            while (!deque.isEmpty()&&nums[deque.peekLast()]<nums[i]){
                deque.pollLast();
            }
            // 记录当前元素的下标
            deque.offerLast(i);
            // 记录最大值
            if(i>=k-1){
                result[i-k+1]=nums[deque.peekFirst()];
            }
        }
        return result;
    }
}
